package training;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_8_6_Training {
    //水果成篮 3
    class SegmentTree {
        private int[] tree;
        private int n;
        private int size;

        public SegmentTree(int[] data) {
            // 单点/区间存储篮子容量的最大值
            // 线段树大小取 2 * 2^{⌈log2 n⌉}
            this.n = data.length;
            this.size = 1;
            while (this.size < n) {
                this.size *= 2;
            }
            this.tree = new int[2 * this.size];
            Arrays.fill(this.tree, -1);

            // 初始化叶子节点（树底层）
            for (int i = 0; i < n; i++) {
                this.tree[this.size + i] = data[i];
            }

            // 自底向上，构建区间最大值
            for (int i = this.size - 1; i > 0; i--) {
                this.tree[i] = Math.max(this.tree[i * 2], this.tree[i * 2 + 1]);
            }
        }

        public void update(int pos, int value) {
            // 将位置 pos 叶子节点更新为 value
            pos += this.size;
            this.tree[pos] = value;

            // 然后向上更新其祖先节点的最大值
            while (pos > 1) {
                pos /= 2;
                this.tree[pos] = Math.max(this.tree[2 * pos], this.tree[2 * pos + 1]);
            }
        }

        public int query(int l, int r) {
            // 查询区间 [l, r) 内的最大值
            l += this.size;
            r += this.size;
            int res = -1;

            // 不断向上
            while (l < r) {
                if (l % 2 == 1) {
                    res = Math.max(res, this.tree[l]);
                    l++;
                }
                if (r % 2 == 1) {
                    r--;
                    res = Math.max(res, this.tree[r]);
                }
                l /= 2;
                r /= 2;
            }

            return res;
        }

        public int findFirst(int qty) {
            int l = 0, r = this.n;
            int res = -1;

            // 二分查找第一个区间最大值 >= qty 的位置
            while (l < r) {
                int m = (l + r) / 2;
                // 满足，说明这个区间里有篮子容量满足条件
                if (this.query(0, m + 1) >= qty) {
                    res = m;
                    r = m;
                } else {  // 否则，更换区间
                    l = m + 1;
                }
            }

            return res;
        }
    }

    class Solution {
        public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
            SegmentTree tree = new SegmentTree(baskets);
            int ans = 0;

            for (int qty : fruits) {
                // 找第一个容量 >= 当前水果重量的篮子
                int idx = tree.findFirst(qty);
                if (idx == -1) {
                    // 找不到合适篮子，水果无法放置
                    ans++;
                } else {
                    // 找到后，更新该篮子为-1表示已使用
                    tree.update(idx, -1);
                    baskets[idx] = -1;
                }
            }

            return ans;
        }
    }

}
